Image data processing, whether for printing or display applications, involves the conversion of display list instructions to bit-mapped data. The display list that is rasterized may be the result of interpretation of higher level instructions, such as those provided by a page description language. The conversion process is often referred to as "raster image processing". The process is also referred to as "scan conversion", even when the display device is other than a cathode ray tube.
The raster image processing may be performed with a multiprocessor system, where multiple processors share raster image processing tasks. On many multiprocessor systems, bandwidth is critical because a single bus must serve a number of processors.
Certain image data processing tasks have been implemented with algorithms that are efficient with respect to computational speed, but not with respect to bandwidth efficiency. One such processing task is image transformation. Image transformation includes operations such as rotation, translation, scaling, and shearing of images. Given a source region and a destination region, the objective is to map an image in the source region to its transform in the destination region.
An image transformation is performed in two steps. The first step is the "interpretation" step. First, the outline of the transformed image in the destination space is clipped to the current clip path. Then, the clipped outline is reduced to trapezoids and run-arrays. The second step is the "rasterization" step. Once the trapezoids are defined in destination space, each pixel in the trapezoid must correspond to a pixel in the source image. Pixel values in the destination space are calculated with a mathematical transformation algorithm.
Conventionally, the rasterization step of transformation is performed one line of a trapezoid at a time. Data caches have been used to assist in providing real time transformations, but conventional data cache methods are implemented on a scan-line basis, which limits their usefulness. For example, a conventional data cache might receive a line of the source image. In the case of a transformation where the image is to be rotated 45 degrees, each pixel in the source space maps to a different line in the destination space. Thus, a new line must be cached to generate each new pixel in the destination space.